package LeetCode.leetcode707;


public class MLinkList {

    private Node virtualNode;

    public MLinkList() {
        virtualNode = new Node();
    }

    /**
     * @param index
     * @return
     */
    public int get(int index) {
        if (index < 0)
            return -1;
        Node p = virtualNode;
        for (int i = 0; i <= index; i++) {
            if (p.next != null)
                p = p.next;
            else
                return -1;
        }
        return p.val;
    }

    /**
     * @param val
     */
    public void addAtHead(int val) {
        Node firstNode = new Node();
        firstNode.val = val;
        firstNode.next = virtualNode.next;
        virtualNode.next = firstNode;
    }

    /**
     * @param val
     */
    public void addAtTail(int val) {
        Node p = virtualNode;
        while (p.next != null) {
            p = p.next;
        }
        Node tailNode = new Node();
        tailNode.val = val;
        p.next = tailNode;
    }

    /**
     * @param index
     * @param val
     */
    public void addAtIndex(int index, int val) {
        if (index <= 0)
            addAtHead(val);
        else {
            Node p = virtualNode;
            int i = 0;
            for (i = 0; i < index; i++) {
                if (p.next != null) {
                    p = p.next;
                } else {
                    break;
                }
            }
            //找到插入位置
            if (i == index) {
                Node insertNode = new Node();
                insertNode.val = val;
                insertNode.next = p.next;
                p.next = insertNode;
            }
        }
    }

    /**
     * @param index
     */
    public void deleteAtIndex(int index) {
        if (index < 0)
            return;
        Node p = virtualNode;
        for (int i = 0; i < index; i++) {
            if (p.next != null) {
                p = p.next;
            } else {
                return;
            }
        }
        if (p.next != null)
            p.next = p.next.next;
    }

    public static class Node {
        int val;
        Node next;
    }
}
